package 动态规划;

public class StickersToSpellWord {

    public static int minStickers1(String[] stickers, String target) {
        int ans = process1(stickers, target);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    // 所有贴纸stickers，每一种贴纸都有无穷张
    // 返回搞定target
    // 最少张数
    public static int process1(String[] stickers, String target) {
        if (target.length() == 0) {
            return 0;
        }
        int min = Integer.MAX_VALUE;
        for (String first : stickers) {
            String rest = minus(target, first); // 每一张贴纸作为第一张
            if (rest.length() != target.length()) {  // 第一张贴纸剪完后得长度 和 原来一样 就没必要继续了

                min = Math.min(min, process1(stickers, rest));
            }
        }
        return min + (min == Integer.MAX_VALUE ? 0 : 1);
    }


    public static String minus(String s1, String s2) {
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        int[] count = new int[26];
        for (char cha : str1) {
            count[cha - 'a']++;
        }
        for (char cha : str2) {
            count[cha - 'a']--;
        }
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < 26; i++) {
            if (count[i] > 0) {
                for (int j = 0; j < count[i]; j++) {
                    builder.append((char) (i + 'a'));
                }
            }
        }
        return builder.toString();
    }


    public static int minStickers2(String[] stickers, String target) {
        int N = stickers.length;
        // 关键优化（用词频表来代替贴纸数组）
        int[][] counts = new int[N][26];
        for (int i = 0; i < N; i++) {
            char[] str = stickers[i].toCharArray();
            for (char cha : str) {
                counts[i][cha - 'a']++;
            }
        }
        int ans = process2(counts, target);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }


    // stickers[i] 数组，当初 i号贴纸得字符统计    int[][] stickers
    public static int process2(int[][] stickers, String t) {
        if (t.length() == 0) {
            return 0;
        }
        // target做出词频统计
        // target aabbc  2 2 1..
        //               0 1 2
        char[] target = t.toCharArray();
        int[] tcounts = new int[26];
        for (char cha : target){
            tcounts[cha - 'a']++;
        }

        int N = stickers.length;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            // 尝试第一张贴纸是谁
            int[] sticker = stickers[i];
            // 最关键优化（重要得是剪枝，这一步也是贪心）
            if (sticker[target[0] - 'a'] > 0){
                StringBuilder builder  = new StringBuilder();
                for (int j = 0; j < 26; j++) {

                }
            }
        }
        return 0;
    }

}
